
#include <iostream>
#include <math.h>
#include <vector>
using namespace std;

// 找到背包可以装的最大价值
int goal_max(vector<pair<int, int>> pj, int v) {
    int n = pj.size();
    // 使用背包DP来解决
    vector<int> dp(v + 1);              // 使用一维数组解决
    for (int i = 1; i <= n ; i++) {
        for (int j = v ; j >= pj[i - 1].first ; j--) {  // 修改遍历顺序,以及结束条件
            int weight = pj[i - 1].first;
            dp[j] = max(dp[j], dp[j - weight] + pj[i - 1].second);
        }
    }
    return dp[v];
}

// 背包恰好装满的情况下 , 的最大价值
int Full_max(vector<pair<int, int>> pj, int v) {
    int n = pj.size();
    // 使用背包DP来解决
    vector<int> dp(v + 1);
    for(int i = 1 ; i <= v ; i++)
        dp[i] = -1;
    for (int i = 1; i <= n ; i++) {         // 修改遍历顺序,以及结束条件
        for (int j = v ; j >= pj[i - 1].first; j--) {
            int weight = pj[i - 1].first;
            if (dp[j - weight] != -1) dp[j] = max(dp[j], dp[j - weight] + pj[i - 1].second);
        }
    }
    return dp[v] == -1 ? 0 :dp[v];
}


int main() {
    int V, n;
    cin >> n >> V;
    vector<pair<int, int>> project(n);
    for (int i = 0 ; i < n ; i++) {
        auto& pr = project[i];
        cin >> pr.first >> pr.second;
    }

    cout << goal_max(project , V) << endl;
    cout << Full_max(project , V) << endl;

    return 0;
}
